package demo2;

import java.util.*;

class TreeNode{
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;
     public TreeNode(int val) {
         this.val = val;
     }
}

public class Solution {

    public boolean IsBalanced_Solution (TreeNode pRoot) {
        return dfs(pRoot) != -1;
    }

    public int dfs(TreeNode root){
        if(root == null) { return 0;}

        int left = dfs(root.left);
        if(left < 0) {return -1;}

        int right = dfs(root.right);
        if(right < 0) { return -1;}

        return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
    }
}
